#include <Trie.hpp>
#include <iostream>
#include <stack>

// Construtor
Trie::Trie(Trie * dad, char dadConnection) : qtyChildren(0) {
	children = std::vector<Trie *>(52, (Trie*)0);
	values = false;
	this->dad = dad;
	this->dadConnection = dadConnection;
}

// Destrutor
Trie::~Trie() {
	if (qtyChildren)
		for (int i = 0; i < 52; i++)
			if (children[i])
				delete children[i];
}

// Metodo de suporte que converte ASCII em indice
int Trie::convertToIndice(char letter) {
	if (letter >= 'a' && letter <= 'z')
		return letter - 'a';
	else if (letter >= 'A' && letter <= 'Z')
		return (letter - 'A') + 26;
	else return -1;
}


// Insere valor na trie
void Trie::insert(std::string& word) {
	int sz = word.length();
	// No corrente e' o no atual (possivelmente raiz)
	Trie * curnode = this;

	// Itera pela chave
	for (int i = 0; i < sz; i++) {
		int pos = convertToIndice(word[i]);

		// Caso caminho nao exista, cria caminho
		if (!curnode->children[pos]) {
			curnode->children[pos] = new Trie(curnode, (char)pos);
			curnode->qtyChildren++;
		}

		// No corrente e' proximo no do caminho
		curnode = curnode->children[pos];
	}

	// Configura posse de valor
	curnode->values = true;
}


// Faz a mesma coisa que metodo anterior, mas para char* ao inves de string
void Trie::insert(const char * word) {
	Trie * curnode = this;

	for (int i = 0; word[i]; i++) {
		int pos = convertToIndice(word[i]);
		if (!curnode->children[pos]) {
			curnode->children[pos] = new Trie(curnode, (char)pos);
			curnode->qtyChildren++;
		}
		curnode = curnode->children[pos];
	}
	curnode->values = true;
}


// Busca ate qualquer prefixo da chave
Trie* Trie::retrieveUntil(std::string& word) {
	int sz = word.length();
	Trie * curnode = this;

	// Itera pela chave
	for (int i = 0; i < sz; i++) {
		int pos = convertToIndice(word[i]);

		// Se nao possui mais caminho, retorna NULL
		if (!curnode->children[pos])
			return 0;

		// Avanca no caminho
		curnode = curnode->children[pos];
		
		// Se posicao atual possui valor (prefixo valido da chave)
		if (curnode->values) {
			// Altera chave
			word = word.substr(0, i+1);
			// Retorna no
			return curnode;
		}
	}
	// Retorna no, se possuir valor
	return curnode->values ? curnode : 0;
}


// Faz a mesma coisa que o metodo anterior, mas para char * ao inves de string
Trie* Trie::retrieveUntil(char * word) {
	Trie * curnode = this;

	for (int i = 0; word[i]; i++) {
		int pos = convertToIndice(word[i]);
		if (!curnode->children[pos])
			return 0;
		curnode = curnode->children[pos];
		
		if (curnode->values) {
			word[i+1] = 0;
			return curnode;
		}
	}
	return curnode->values ? curnode : 0;
}

// Retorna no associado a chave, caso no possua valor
// e NULL, caso contrario
Trie* Trie::retrieve(std::string word) {
	int sz = word.length();
	Trie * curnode = this;

	// Itera pela chave
	for (int i = 0; i < sz; i++) {
		int pos = convertToIndice(word[i]);

		// Se nao possui caminho, retorna NULL
		if (!curnode->children[pos])
			return 0;

		// Avanca pelo caminho
		curnode = curnode->children[pos];
	}

	// Retorna o no, se possuir valor
	return curnode->values ? curnode : 0;
}

// Faz a mesma coisa que o metodo anterior, mas para char * ao inves de string
Trie* Trie::retrieve(const char * word) {
	Trie * curnode = this;

	for (int i = 0; word[i]; i++) {
		int pos = convertToIndice(word[i]);
		if (!curnode->children[pos])
			return 0;
		curnode = curnode->children[pos];
	}
	return curnode->values ? curnode : 0;
}


// Serializa uma string atraves de uma busca em profundidade
void Trie::serialize(std::ostream& stream, int head) {

	std::list<int>::iterator it, itEnd;

	// Passa pelos filhos
	for(int it = 0; it != 52; it++) {
		if (!children[it]) continue;
		// Imprime o caracter de conexao para efetuar serializacao
		stream << convertToChar(it);
		// Serializa o filho (basicamente, se nao tiver mais filhos, coloca . ou !)
		children[it]->serialize(stream, head + 1);
	}
	// Coloca . se nao tiver valores ou ! caso contrario
	if (!values)
		stream << '.';
	else
		stream << '!';
}

// Deserializa
int Trie::deserialize(std::istream& stream) {
	char curr;
	std::string str, key;
	// Buffer de palavra
	char buffer[1024];
	int head = 0;
	buffer[0] = 0;
	int counter = 0;
	for (;;) {
		stream >> curr;
		// Sai de no sem valor
		if (curr == '.') {
			if(!head) break;
			head--;
			buffer[head] = 0;

		// Sai de no com valor
		} else if (curr == '!') {
			str = buffer;
			// Insere valor
			insert(str);
			// Incrementa contador de chaves distintas
			counter++;
			if(!head) break;
			head--;
			buffer[head] = 0;

		// Letra pertencente a chave
		} else {
			buffer[head] = curr;
			head++;
			buffer[head] = 0;
		}
	}

	// Retorna quantidade de chaves distintas
	return counter;
}


// Metodo de suporte que converte indice em ASCII
char Trie::convertToChar(int pos) {
	if (pos < 26) return 'a' + (char)pos;
	else return 'A' + ((char)pos - 26);
}


void Trie::remove() {

	// Remove valor
	values = false;
	Trie * curnode = this;

	// Se possui filhos ou e' raiz, nao faz mais nada
	if (curnode->qtyChildren || !curnode->dad) return;

	// Deleta o no da memoria e todos os nos pais que nao tenham
	// mais filhos
	do {
		Trie * dad = curnode->dad;
		dad->children[curnode->dadConnection] = 0;
		dad->qtyChildren--;
		delete curnode;
		curnode = dad;
	} while(curnode->dad && !curnode->values && !curnode->qtyChildren);
}

